A primary way for an attacker to corrupt a privileged program's behavior is to corrupt code and data pointers stored in the program's address space, and then cause the program to depend on those corrupted values. Below we describe several variations on this attack. Below we present past defenses against these vulnerabilities.
Variations on the Vulnerability Problem
These vulnerabilities are unfortunately common in C programs, due to C's weak typing system. C is a widely used programming language in both systems and applications programs. The variations on this attack method are:
How to corrupt a variable: The C programming language, which is widely used for both systems and applications programming, is weakly typed, leading to a variety of ways that the attacker can fool the program into corrupting itself, such as buffer overflows and printf format bugs. We survey these methods below.
Possible effects of corrupting a variable: By changing the value of some variable in a program, the attacker can compromise the function of the program in various ways, causing the privileged program to do something unanticipated by the programmer and advantageous to the attacker. We survey these possible effects below.
Ways to Corrupt a Variable
There are a variety of ways for the attacker to corrupt a variable in a victim program. By far the two most common methods are buffer overflows and printf format bugs:
Buffer overflows: It is common to C programs to not do strict bounds checking on the size of input strings provided to the program. If the attacker provides more input than the program provided for, then the buffer is overflowed, and the attacker's input overwrites whatever is adjacent to the buffer. Attackers commonly look for programs that have overflowable buffers adjacent to security-sensitive variables. Below we detail the problems and previous solutions for buffer overflow vulnerabilities.
Printf format string bugs: This is a new form of vulnerability in C programs that has rapidly become common after initial discovery in spring 2000. When it occurs, it allows the attacker to cause calls to the printf function to write an arbitrary word to an arbitrary location in the program's address space. Below we give specific details on printf format string vulnerabilities.
Possible Effects of Corrupting a Variable
By corrupting a variable in the program's state, the attacker can cause the program to behave in unexpected ways. In principle, the attacker can cause arbitrary behavior by changing an arbitrary variable. In practice, the variable that can be modified is often determined by the nature of the defect in the victim program, and so the attacker does not have total choice over which variable to change. Furthermore, most programs do not have functionality of interest to the attacker, and so causing aberrant behavior in the program does not satisfy the attacker's goals.
For these reasons, the attacker most desires to get the victim program to execute arbitrary code, referred to as “shell code” in the hacker underground community. To get the program to execute “shell code,” the attacker must modify a code pointer (a pointer that the program expects to point to legitimate code) such that the code pointer points to code the attacker would like executed. Once the code pointer has been thus modified, at some later point in execution the program dereferences the corrupted code pointer, and instead of jumping to the intended code, the program jumps to the attacker's “shell code.” There are three kinds of code pointers that the attacker can modify:
Activation records: Each time a function is called, it lays down an activation record on the stack that includes, among other things, the return address that the program should jump to when the function completes. Attacks that corrupt activation record return addresses overflow automatic variables, i.e., buffers local to the function, as shown in FIG. 1. By corrupting the return address in the activation record, the attacker causes the program to jump to attack code when the victim function returns and dereferences the return address. This form of buffer overflow is called a “stack smashing attack” and is the most popular code pointer for attackers to try to modify.
Function pointers: “Void (* foo)( )” declares the variable foo which is of type “pointer to function returning void.” Function pointers can be allocated anywhere (stack, heap, static data area) and so the attacker need only find an overflowable buffer adjacent to a function pointer in any of these areas and overflow it to change the function pointer. Some time later, when the program makes a call through this function pointer, it will instead jump to the attacker's desired location. An example of this kind of attack appeared in an attack against the superprobe program for Linux.
Longjmp buffers: C includes a simple checkpoint/rollback system called setjmp/longjmp. The idiom is to say “setjmp(buffer)” to checkpoint, and say “longjmp(buffer)” to go back to the checkpoint. However, if the attacker can corrupt the state of the buffer, then “longjmp(buffer)” will jump to the attacker's code instead. Like function pointers, longjmp buffers can be allocated anywhere, so the attacker need only find an adjacent overflowable buffer. An example of this form of attack appeared against Perl 5.003. The attack first corrupted a longjmp buffer used to recover when buffer overflows are detected, and then induces the recovery mode, causing the Perl interpreter to jump to the attack code.
The attacker may further attempt an indirect method to corrupt a code pointer by corrupting some other pointer (typically a string pointer) to point at or near a code pointer. When the program then writes data back to the other pointer, it has the effect of corrupting the code pointer.
It also matters where the code pointer to be corrupted is located: on the stack, in the heap, or in the static data area. However, this distinction only matters with respect to various kinds of defenses that can be employed against code pointer corruption, and so we will address it below.
Previous Defenses
Previous defenses against code pointer corrupting come in several forms. In the sections below we describe the following: (1) simple expedients of writing correct code; (2) methods that make various segments of memory non-executable; (3) array bounds checking methods; (4) type-safe programming languages; and (5) code pointer integrity checking methods, which is the same family as our PointGuard invention.
Writing Correct Code
“To err is human, but to really foul up requires a computer.”—Anon. Writing correct code is a laudable but remarkably expensive proposition, especially when writing in a language such as C that has error-prone idioms such as null-terminated strings and a culture that favors performance over correctness. Despite a long history of understanding of how to write secure programs vulnerable programs continue to emerge on a regular basis. Thus some tools and techniques have evolved to help novice developers write programs that are somewhat less likely to contain buffer overflow vulnerabilities.
The simplest method is to grep the source code for highly vulnerable library calls such as strcpy and sprintf that do not check the length of their arguments. Versions of the C standard library have also been developed that complain when a program links to vulnerable functions like strcpy and sprintf.
Code auditing teams have appeared with an explicit objective of auditing large volumes of code by hand, looking for common security vulnerabilities such as buffer overflows and file system race conditions. However, buffer overflow vulnerabilities can be subtle. Even defensive code that uses safer alternatives such as strncpy and snprintf can contain buffer overflow vulnerabilities if the code contains an elementary off-by-one error. For instance, the lprm program was found to have a buffer overflow vulnerability, despite having been audited for security problems such as buffer overflow vulnerabilities.
To combat the problem of subtle residual bugs, more advanced debugging tools have been developed, such as fault injection tools. The idea is to inject deliberate buffer overflow faults at random to search for vulnerable program components. There are also static analysis tools emerging that can detect many buffer overflow vulnerabilities.
While these tools are helpful in developing more secure programs, C semantics do not permit them to provide total assurance that all buffer overflows have been found. Debugging techniques can only minimize the number of buffer overflow vulnerabilities, and provide no assurances that all the buffer overflow vulnerabilities have been eliminated. Thus, for high assurance, protective measures such as those described below should be employed unless one is very sure that all potential buffer overflow vulnerabilities have been eliminated.
Non-Executable Memory Segments
The general concept is to make the data segment of the victim program's address space non-executable, making it impossible for attackers to execute the code they inject into the victim program's input buffers. This is actually the way that many older computer systems were designed, but more recent UNIX and MS Windows systems have come to depend on the ability to emit dynamic code into program data segments to support various performance optimizations. Thus one cannot make all program data segments non-executable without sacrificing substantial program compatibility.
However, one can make the stack segment non-executable and preserve most program compatibility. Kernel patches are available for both Linux and Solaris that make the stack segment of the program's address space non-executable. Since virtually no legitimate programs have code in the stack segment, this causes few compatibility problems. There are two exceptional cases in Linux where executable code must be placed on the stack:
Signal delivery: Linux delivers UNIX signals to processes by emitting code to deliver the signal onto the process's stack and then inducing an interrupt that jumps to the delivery code on the stack. The non-executable stack patch addresses this by making the stack executable during signal delivery.
GCC trampolines: There are indications that gcc places executable code on the stack for “trampolines.” However, in practice disabling trampolines has never been found to be a problem; that portion of gcc appears to have fallen into disuse.
The protection offered by non-executable stack segments is highly effective against attacks that depend on injecting attack code into automatic variables but provides no protection against other forms of attack. Attacks exist that bypass this form of defense by pointing a code pointer at code already resident in the program. Other attacks could be constructed that inject attack code into buffers allocated in the heap or static data segments.
Array Bounds Checking
While injecting code is optional for a buffer overflow attack, the corruption of control flow is essential. Thus unlike non-executable buffers, array bounds checking completely stops buffer overflow vulnerabilities and attacks. If arrays cannot be overflowed at all, then array overflows cannot be used to corrupt adjacent program state.
To implement array bounds checking, then all reads and writes to arrays need to be checked to ensure that they are within range. The direct approach is to check all array references, but it is often possible to employ optimization techniques to eliminate many of these checks. There are several approaches to implementing array bounds checking, as exemplified by the following projects.
Compaq C Compiler
The Compaq C compiler for the Alpha CPU (cc on Tru64 UNIX, ccc on Alpha Linux) supports a limited form of array bounds checking when the “-check_bounds” option is used. The bounds checks are limited in the following ways:                only explicit array references are checked, ie., “a” is checked, while “*(a+3)” is not        since all C arrays are converted to pointers when passed as arguments, no bounds checking is performed on accesses made by subroutines        dangerous library functions (i.e., strcpy( )) are not normally compiled with bounds checking, and remain dangerous even with bounds checking enabled        
Because it is so common for C programs to use pointer arithmetic to access arrays, and to pass arrays as arguments to functions, these limitations are severe. The bounds checking feature is of limited use for program debugging, and no use at all in assuring that a program's buffer overflow vulnerabilities are not exploitable.
Jones & Kelly: Array Bounds Checking for C
Richard Jones and Paul Kelly developed a gcc patch that does full array bounds checking for C programs. Compiled programs are compatible with other gcc modules, because they have not changed the representation of pointers. Rather, they derive a “base” pointer from each pointer expression, and check the attributes of that pointer to determine whether the expression is within bounds.
The performance costs are substantial: a pointer-intensive program (ijk matrix multiply) experienced 30× slowdown, Since slowdown is proportionate to pointer usage, which is quite common in privileged programs, this performance penalty is particularly unfortunate.
The compiler did not appear to be mature; complex programs such as elm failed to execute when compiled with this compiler. However, an updated version of the compiler is being maintained, and it can compile and run at least portions of the SSH software encryption package. Throughput experiments with the updated compiler and software encryption using SSH showed a 12× slowdown (see below for comparison).
Purify: Memory Access Checking
Purify is a memory usage debugging tool for C programs. Purify uses “object code insertion” to instrument all memory accesses. After linking with the Purify linker and libraries, one gets a standard native executable program that checks all of its array references to ensure that they are legitimate. While Purify-protected programs run normally without any special environment, Purify is not actually intended as a production security tool: Purify protection imposes a 3 to 5 times slowdown.
Type-Safe Languages
Buffer overflow vulnerabilities result from the lack of type safety in C. If only type-safe operations can be performed on a given variable, then it is not possible to use creative input applied to variable foo to make arbitrary changes to the variable bar. If new, security-sensitive code is to be written, it is recommended that the code be written in a type-safe language such as Java or ML.
Unfortunately, there are millions of lines of code invested in existing operating systems and security-sensitive applications, and the vast majority of that code is written in C. This paper is primarily concerned with methods to protect existing code from buffer overflow attacks.
However, it is also the case that the Java Virtual Machine (JVM) is a C program, and one of the ways to attack a JVM is to apply buffer overflow attacks to the JVM itself. Because of this, applying buffer overflow defensive techniques to the systems that enforce type safety for type-safe languages may yield beneficial results.
Defenses Specific to Printf Format String Vulnerabilities
In June 2000, a major new class of vulnerabilities called “format bugs” was discovered. The problem is that there exists a % n format token for C's printf format strings that commands printf to write back the number of bytes formatted so far to the corresponding argument to printf, presuming that the corresponding argument exists, and is of type int *. This becomes a security issue if a program permits un-filtered user input to be passed directly as the first argument to printf, and thus forms a new way for attackers to write into the program's address space, and thus modify a pointer value.
This is a common vulnerability because of the (previously) wide-spread belief that format strings are harmless. As a result, literally dozens of format bug vulnerabilities have been discovered in common tools in the ensuing four months.
The abstract cause for format bugs is that C's argument passing conventions are type-unsafe. In particular, the varargs mechanism allows functions to accept a variable number of arguments (e.g., printf) by “popping” as many arguments off the call stack as they wish, trusting the early arguments to indicate how many additional arguments are to be popped, and of what type.
A variety of solutions exist to address format bugs. Various static analysis tools can detect some instances of format bugs, at the expense of false reports of some format bugs, and missing some other instances of format bugs, making the tools costly to use. Our own FormatGuard tool uses argument counting to dynamically detect attempts to exploit format bugs. Full bounds checking as in Jones & Kelly (see above) and type safe languages (see above) stops format bugs, with the usual limitation that full bounds checking is difficult and expensive for C programs.
Code Pointer Integrity Checking
The goal of code pointer integrity checking is subtly different from bounds checking. Instead of trying to prevent corruption of code pointers (see above) code pointer integrity checking seeks to detect that a code pointer has been corrupted before it is dereferenced. Thus while the attacker succeeds in corrupting a code pointer, the corrupted code pointer will never be used because the corruption is detected before each use.
Code pointer integrity checking has the disadvantage relative to bounds checking that it does not perfectly solve the buffer overflow problem; overflows that affect program state components other than code pointers will still succeed. However, it has substantial advantages in terms of performance, compatibility with existing code, and implementation effort.
Code pointer integrity checking has been studied at three distinct levels of generality. Snarskii developed a custom implementation of libc for FreeBSD that introspects the CPU stack to detect buffer overflows, described below. Our own StackGuard project produced a compiler that automatically generates code to perform integrity checking on function activation records, described below.
Hand-Coded Stack Introspection
Snarskii developed a custom implementation of libc for FreeBSD that introspects the CPU stack to detect buffer overflows. This implementation was hand-coded in assembler, and only protects the activation records for the functions within the libc library. Snarskii's implementation is effective as far as it goes, and protects programs that use libc from vulnerabilities within libc, but does not extend protection to vulnerabilities in any other code.
StackGuard: Compiler-Generated Activation Record Integrity Checking
StackGuard is a compiler technique for providing code pointer integrity checking to the return address in function activation records. StackGuard is implemented as a small patch to gcc that enhances the code generator for emitting code to set up and tear down functions. The enhanced setup code places a “canary” word (a direct descendant of the Welsh miner's canary) next to the return address on the stack, as shown in FIG. 2. The enhanced function tear down code first checks to see that the canary word is intact before jumping to the address pointed to by the return address word. Thus if an attacker attempts a “stack smashing” attack as shown in FIG. 1, the attack will be detected before the program ever attempts to dereference the corrupted activation record.
Critical to the StackGuard “canary” approach is that the attacker is prevented from forging a canary by embedding the canary word in the overflow string. StackGuard employs two alternative methods to prevent such a forgery:
Terminator Canary: The terminator canary is comprised of the common termination symbols for C standard string library functions; 0 (null), CR, LF, and −1 (EOF). The attacker cannot use common C string libraries and idioms to embed these symbols in an overflow string, because the copying functions will terminate when they hit these symbols.
Random Canary: The canary is simply a 32-bit random number chosen at the time the program starts. The random canary is a secret that is easy to keep and hard to guess, because it is never disclosed to anyone, and it is chosen anew each time the program starts.
StackGuard XOR Random Canary
In October 1999, Mariusz Woloszyn <emsi@it.pl> discovered a method to bypass StackGuard's random and terminator canary defenses under special circumstances. Consider this vulnerable code:
Foo (char * arg) {char *  p = arg;   // a vulnerable pointerchar a[25];  // the buffer that makes the pointer vulnerablegets(a);  // using gets( ) makes you vulnerablegets(p);  // this is the good part}
In attacking this code, the attacker first overflows the buffer a[ ] with a goal of changing the value of the char * p pointer. Specifically, the attacker can cause the p pointer to point anywhere in memory, but especially at a return address record in an activation record. When the program then takes input and stores it where p points, the input data is stored where the attacker said to store it.
Wosczin had, in effect, discovered another way to make arbitrary changes to a victim program's address space (the others being buffer overflows and printf format string vulnerabilities). In response to this, Crispin Cowan and Steve Beattie (employed at WireX at the time) invented both the PointGuard “zero space canary” (which we will describe below) and the XOR Random Canary, which we published in November 1999 http://lwn.net/1999/1111/a/stackguard.html
The XOR Random Canary is a new method to preserve the integrity of both the activation record's return address, and the canary. Like the StackGuard random canary mechanism described above, we choose a random canary word at exec ( ) time, but we also XOR the canary with the return address word, so that the return address is bound to the random canary value. The exact procedure is as follows:
Setting up an activation record when calling a function:                1. push the return address        2. look up the random canary word for the current function        3. XOR the random canary word with the return address        4. store the result immediately below the return address in the activation record        
Tearing down an activation record when returning from a function:                1. fetch the canary word from memory        2. XOR the memory canary word with the return address on the stack        3. compare the result with the random canary word associated with the current function        
The result of this method is that we have the same protection as with the classic Random canary, and also the property that the attacker cannot modify the return address without invalidating the canary word.
As in the random canary, a variation on this idea is to associate a different canary word with each function in the program. This provides a degree of resistance to vulnerabilities that might allow the attacker to learn the value of the canary word. In another variation, we choose only a fixed number of canary words (e.g., 128), assign each function in the program an ordinal number, and then associate the random canary number from the canary table by computing the index from the ordinal number modulus the size of the table.
Lee and Tyagi
In June 2000 Lee and Tyagi published a paper in which they propose a CPU architecture enhanced to encrypt the PC (program counter). Lee and Tyagi propose that an encoding function be included in the CPU hardware, and that this hardware decodes the encrypted value just before loading it into the CPU. Their proposed system employed some unusual features in the cryptography to attempt to proactively detect corrupted PC values, rather than just allowing the program to jump to a random location and hoping that it probably will crash.